#include <iostream>
#include "BinarySearchTree.hpp"
#include <ctime>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
void BST_sort(std::vector<T> &_data){
//把向量中的元素加入到树中
    BinarySearchTree<T> t;
    for(int i=0;i<_data.size();i++){
        t.insert(_data[i]);
    }
//清空向量
    _data.clear();
//把树中的元素加入到向量中
    while(!t.isEmpty()){
        T x=t.findMin();
        t.remove(x);
        _data.push_back(x);
    }
}

template <typename T>
void Randomized_BST_sort(std::vector<T> &_data){
//打乱向量中的元素
    random_shuffle(_data.begin(),_data.end());
    BST_sort(_data);
}

int main(){
    srand((unsigned)time(NULL));
//定义两个向量a,b
    vector<int> a,b;
//随机生成10000个小于131072的元素
    for(int i = 0; i < 10000; i++){
        a.push_back(rand() & 131071);
    }
    b=a;
//输出向量a和b
    cout << "The followings are vector a and b." << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;
    for(int i = 0; i < b.size(); i++)
        cout << b[i] << "\t";
    cout << endl;
//记录两个排序的方法所用的时间
    int ta = clock();
    BST_sort(a);
    cout << "FinishedTime: " << (double) (clock() - ta)/ CLOCKS_PER_SEC *1000   << "ms" << std::endl;

    int tb = clock();
    Randomized_BST_sort(b);
    cout << "FinishedTime: " << (double) (clock() - tb)/ CLOCKS_PER_SEC *1000   << "ms" << std::endl;
//输出向量a和b
    cout << "The following are the ordered vector a and b.!" << endl;
    for(int i = 0; i < a.size(); i++)
        cout << a[i] << "\t";
    cout << endl;
    for(int i = 0; i < b.size(); i++)
        cout << b[i] << "\t";
    cout << endl;

    return 0;
}
